using System;
using System.Collections.Generic;

namespace Test.ConsoleProgram.Algorithm.Solution
{
    [TestDescription("算法: 1356. 根据数字二进制下 1 的数目排序")]
    public class No1356_SortByBits : AbsBaseTestItem
    {
        /*
        给你一个整数数组 arr 。请你将数组中的元素按照其二进制表示中数字 1 的数目升序排序。
        如果存在多个数字二进制中 1 的数目相同，则必须将它们按照数值大小升序排列。
        请你返回排序后的数组。
        提示：
            1 <= arr.length <= 500
            0 <= arr[i] <= 10^4
        */

        public override void OnTest()
        {
            Assert.TestExe(SortByBits,
                new int[] { 0, 1, 2, 3, 4, 5, 6, 7, 8 },
                new int[] { 0, 1, 2, 4, 8, 3, 5, 6, 7 });
            Assert.TestExe(SortByBits,
                new int[] { 1024, 512, 256, 128, 64, 32, 16, 8, 4, 2, 1 },
                new int[] { 1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024 });
            Assert.TestExe(SortByBits,
                new int[] { 10000, 10000 },
                new int[] { 10000, 10000 });
            Assert.TestExe(SortByBits,
                new int[] { 2, 3, 5, 7, 11, 13, 17, 19 },
                new int[] { 2, 3, 5, 17, 7, 11, 13, 19 });
            Assert.TestExe(SortByBits,
                new int[] { 10, 100, 1000, 10000 },
                new int[] { 10, 100, 10000, 1000 });
        }

        public int[] SortByBits(int[] arr)
        {
            int cale_bitCount(int a)
            {
                if (a == 0) return 0;
                int count = 0;
                while (a > 2)
                {
                    count += a % 2;
                    a = a / 2;
                }
                return count++;
            }
            var dic_bitCount = new Dictionary<int, int>();
            int n = arr.Length;
            var ans = new int[n];
            for (int i = 0; i < n; i++)
            {
                var key = arr[i];
                ans[i] = key;
                if (dic_bitCount.ContainsKey(key)) continue;
                dic_bitCount[key] = cale_bitCount(key);
            }
            Array.Sort(ans, (x, y) =>
            {
                var x_bit = dic_bitCount[x];
                var y_bit = dic_bitCount[y];
                if (x_bit == y_bit)
                    return x < y ? -1 : 1;
                return x_bit < y_bit ? -1 : 1;
            });
            return ans;
        }
    }
}
